// @coding: utf8

#include <iostream>
#include <cstdint>
#include <vector>
#include <unordered_map>

const uint64_t kZSkipListMaxLevel = 32;

template <typename TKey, typename TValue>
struct ZSkipListNode
{
    ZSkipListNode(uint32_t level = kZSkipListMaxLevel)
    {
        forward.resize(level);
        std::fill(forward.begin(), forward.end(), nullptr);
    }

    ZSkipListNode(const TKey& k, const TValue& v, uint32_t level = kZSkipListMaxLevel) :
        key(k), value(v)
    {
        forward.resize(level);
        std::fill(forward.begin(), forward.end(), nullptr);
    }

    TKey key;
    TValue value;
    // uint32_t level
    std::vector<ZSkipListNode<TKey, TValue>> forward;  // 层级指针
    //ZSkipListNode<TKey, TValue>* forward;
};

template <typename TKey, typename TValue>
struct ZSkipListLevel
{
    ZSkipListNode<TKey, TValue>* forward;
    uint64_t span;
};

// @brief 跳表
// 1.最底层lv0时一张完整的链表,假设长度为n
// 2.lv1层有n/2个索引，lv2有n/4个索引，以此类推每一层减少一半。这个分布规则通过随机实现，每次随机[1，max_lv],结果作为当前节点是否需要作为索引
template <typename TKey, typename TValue>
class ZSkipList
{
    // type traits
    typedef ZSkipListNode<TKey, TValue> zskiplist_node_t;
    typedef TKey key_t;
    typedef TValue value_t;
public:
    int size() { return _cnt; }
    uint64_t insert(const key_t& key, const value_t& value)
    {
        zskiplist_node_t* cur_node = _header;
        // 从高网低搜素
        for (int level = _cur_level - 1; level >= 0; --level)
        {
            // 当前lv存在
            while (cur_node->forward[level] &&
                cur_node->forward[level]->value <= value &&
                cur_node->forward[level]->key < key)
            {
                cur_node = cur_node->forward[level]->forward;
            }
        }
    }

    bool is_contain(const key_t& key);

protected:

protected:
    int _max_level;  // 最大层数
    int _cur_level;  // 当前层数
    zskiplist_node_t* _header;  // 头节点
    uint64_t _cnt;  // 当前大小
};

template <typename TKey, typename TValue>
ZSkipListNode<TKey, TValue>* create_zskip_list_node(int level, const TKey& key, const TValue& value)
{
    auto node = new ZSkipListNode<TKey, TValue>;
}

int main()
{
    return 0;
}